#include <iostream>
#include <vector>
#include <xmemory>
#include "conio.h"

using namespace std;

const int carol_prime_number = 1046527;

struct List_node
{
	List_node() : next(nullptr), prev(nullptr) {}

	int elem;
	List_node *next,
		*prev;
};

class DL_list
{
public:
	DL_list() { root = nullptr; }
	
	~DL_list()
	{
		if (root == nullptr)
			return;

		List_node *cur_elem = root;
		do 
		{
			List_node *next_elem = cur_elem->next;
			delete cur_elem;
			cur_elem = next_elem;
		} while (cur_elem != root);
	}

	void add(int elem)
	{
		List_node *ln = new List_node;
		ln->elem = elem;

		if (root == nullptr)
		{
			root = ln;
			root->next = root;
			root->prev = root;
		}
		else
		{
			List_node *root_next = root->next;
			root->next = ln;
			root_next->prev = ln;
			ln->prev = root;
			ln->next = root_next;
		}
	}

	bool is_empty() const
	{
		return root == nullptr;
	}

	int n_elements() const
	{
		if (root == nullptr)
			return 0;

		List_node *cur_elem = root;
		int n_elements = 0;
		do 
		{
			cur_elem = cur_elem->next;
			++n_elements;
		} while (cur_elem != root);

		return n_elements;
	}

	bool contains(int elem) const
	{
		if (root == nullptr)
			return false;

		List_node *cur_elem = root;
		do 
		{
			if (cur_elem->elem == elem)
				return true;
			cur_elem = cur_elem->next;
		} while (cur_elem != root);

		return false;
	}

	vector<int> elements() const
	{
		vector<int> res;
		if (root == nullptr)
			return res;

		List_node *cur_elem = root;
		do 
		{
			res.push_back(cur_elem->elem);
			cur_elem = cur_elem->next;
		} while (cur_elem != root);

		return res;
	}

private:
	List_node *root;
};

class Hash_table
{
public:
	Hash_table() 
	{
		initialize(1, 5, 5, 1);
	}

	void initialize(int a, int b, int p, int m)
	{
		this->a = a;
		this->b = b;
		this->p = p;
		this->m = m;
		table.resize(m);

		for (int i_bucket = 0; i_bucket < m; ++i_bucket)
			table[i_bucket] = shared_ptr<DL_list>(new DL_list());
	}

	void add(int elem)
	{
		int idx = h(elem);
		shared_ptr<DL_list> l = table[idx];
		l->add(elem);
	}

	int h(int elem) const
	{
		return ((a*elem + b) % p) % m;
	}

	bool perfect_hash() const
	{
		for (int i_backet = 0; i_backet < table.size(); ++i_backet)
		{
			if (table[i_backet]->n_elements() > 1)
				return false;
		}

		return true;
	}

	shared_ptr<DL_list> get_bucket(int i_bucket) const
	{
		return table[i_bucket];
	}

	bool contains(int elem) const
	{
		return table[h(elem)]->contains(elem);
	}

// 	Hash_table& operator= (const Hash_table &h)
// 	{
// 		if (this == &h)
// 			return;
// 		this->a = h.a;
// 		this->b = h.b;
// 		this->p = h.p;
// 		this->m = h.m;
// 		
// 		this->table.resize(h.table.size());
// 		for (int i_elem = 0; i_elem < table.size(); ++i_elem)
// 			this->table[i_elem] = h.table[i_elem];
// 
// 		return *this;
// 	}

private:
	int a, b, p, m;
	vector<shared_ptr<DL_list>> table;
};

class Fixed_set 
{
public:
	Fixed_set() {};

	void initialize(const vector<int>& numbers)
	{

		int first_level_hash_size = numbers.size() * first_level_hash_size_multiplier;
		first_level_hash.initialize(10, 15, carol_prime_number, first_level_hash_size);

		for (int i_num = 0; i_num < numbers.size(); ++i_num)
			first_level_hash.add(numbers[i_num]);

		second_level_hashes.resize(first_level_hash_size);

		// building second-level prefect hashes
		for (int i_bucket = 0; i_bucket < first_level_hash_size; ++i_bucket)
		{
			shared_ptr<DL_list> bucket = first_level_hash.get_bucket(i_bucket);
			if (!bucket->is_empty())
			{
				bool found_perfect_hash = false;
				Hash_table *hash_candidate = new Hash_table;
				while (!found_perfect_hash)
				{
					int a = rand() % 1000,
						b = rand() % 1000;
					hash_candidate->initialize(a, b, carol_prime_number, pow(static_cast<double>(bucket->n_elements()), static_cast<int>(2)));

					vector<int> elements = bucket->elements();
					// traversing all elements in the current list					
					for (int i_elem = 0; i_elem < elements.size(); ++i_elem)
					{
						hash_candidate->add(elements[i_elem]);
					}

					if (bucket->n_elements() == 1 || hash_candidate->perfect_hash())
						found_perfect_hash = true;
				}

				second_level_hashes[i_bucket] = *hash_candidate;
			}
			else
			{
				second_level_hashes[i_bucket] = Hash_table();
			}
		}
	}

	bool contains(int number) const
	{
		int idx = first_level_hash.h(number);
		return second_level_hashes[idx].contains(number);
	}

private:
	static const int first_level_hash_size_multiplier = 4;

	Hash_table first_level_hash;
	vector<Hash_table> second_level_hashes;
};

void main()
{
	int n_elems_in_the_set;
	cout << "Input set size:" << endl;
	cin >> n_elems_in_the_set;

	cout << "Input set elements:" << endl;
	vector<int> set_elems(n_elems_in_the_set);
	for (int i_elem = 0; i_elem < n_elems_in_the_set; ++i_elem)
		cin >> set_elems[i_elem];

	int n_queries;
	cout << "Input number of queries:" << endl;
	cin >> n_queries;

	cout << "Input queried elements:" << endl;
	vector<int> queries(n_queries);
	for (int i_query = 0; i_query < n_queries; ++i_query)
		cin >> queries[i_query];
	
	Fixed_set fixed_set;
	fixed_set.initialize(set_elems);

	cout << "Containment relationship:" << endl;
	for (int i_query = 0; i_query < n_queries; ++i_query)
	{
		cout << queries[i_query] << " : " << fixed_set.contains(queries[i_query]) << endl;
	}
	_getch();
}